/*
 * Eine Instanz von SortedSet stellt eine als einfache
 * Liste implementierte Menge dar, deren Elemente aufsteigend
 *  sortiert sind. Ein Typparameter bestimmt den Typ der Elemente. 
 *  Die Elemente muessen eine Methode faster mit einem Parameter unterstuetzen, 
 *  die genau dann true zurueckgibt, wenn this (auf nicht naeher bestimmte Weise) 
 *  schneller als das uebergebene Argument ist. 
 *  SortedSet implementiert folgende Methoden:
 *  
 *  -insert nimmt ein Argument, das an geeigneter Stelle eingefuegt wird,
 *   wenn nicht bereits ein identisches Element vorhanden war.
 *    Mehrere gleiche aber nicht identische Elemente duerfen in der Menge sein.
 *    
 *  - iterator liefert als Ergebnis einen Iterator (mit den Methoden next und hasNext),
 *  ueber den nacheinander auf alle Elemente der Menge in aufsteigender Reihenfolge
 *  zugegriffen werden kann.
 */
public class SortedSet<Typ extends fasterInterface<Typ>> implements ListInterface<Typ>
{
	//Leere Liste head = null
	private element head;
	
	//Anzahl aller erzeugten elemente
	private int n;
	
	/*Beim erzeugen einer neuen Liste 
	head = null
	Anzahl der Elemente = 0*/
	
	public SortedSet()
	{
		head = null;
		n = 0;
	}
	
	//Repraesentiert ein Element, wird fuer jedes Element der Liste erzeugt
	protected class element
	{
		//Represent the value of element
		private Typ valueelem; 
		
		//Represent next and previous element
		private element nextelem;
		private element preelem;
		
		//Create the element,set next and previous element
		//IN: Fuse or Racer or ...
		public element (Typ elem) 
		{ 
			this.valueelem = elem; 
			this.nextelem = null;
			this.preelem = null;
		}
		//Gibt nur dann true zurueck, wenn this groesser dem einelesenen element ist
		public boolean faster(Typ that) 
		{
			return this.valueelem.faster(that);
		}
	
		//---Getter---
		// get next element
		//Out: element of SortedList
		protected element getnext()
		{
			return nextelem;
		}
		//get previous element
		// Out: element of SortedList
		protected element getpre()
		{
			return preelem;
		} 
		//get Typ(fuse or Racer) of element
		// Out: Fuse or Racer or ...
		protected Typ getvalue()
		{
			return valueelem;
			
		}		
		//---Setter:
		//set next element
		// IN: element
		public void setnext(element a)
		{
			this.nextelem = a;
		}
		//set previous element
		// IN: element
		public void setpre(element a)
		{
			this.preelem = a;
		}
		//set Value of element
		// IN: Fuse or Racer or ...
		public void setvalue(Typ a)
		{
			this.valueelem = a;
		}		
	}
	
	//Einfuegen eines neuen Elements am bestimmter Position der Liste
	//IN: Typ(Fuse,Racer,...)
	public void insert(Typ newelem) 
	{
		boolean check = true; 
		//Falls Liste leer
		//neues Element = next = previous = head
		if (head == null) 
		{
			// Erzeuge neues Element
			element neu  =  new element(newelem);
			// Setze head = neues Element
			head = neu;
			// das naechste bzw preelement von neu auf neu zeigen lassen
			neu.nextelem = neu;
			neu.preelem = neu;
		}
		//Sonst einfuegen des Elements an bestimmter Position
		else 
		{
			//Erzeugen des neuen Elements
			element neu = new element(newelem);
		
			//ereugen des iterator fuer aktiv liste
			iterator b = new iterator();
			
			//Pointer auf Head
			element temppointer = head;
			
			//Wenn nur ein Element vorhanden + Ueberpruefung auf zwei gleiche elemente
			if(head.valueelem == neu.valueelem)
				check = false;
			
			if(!b.hasNext() && check)
			{
				//Verlinkungen setzen
				neu.nextelem = temppointer;
				neu.preelem = temppointer;
				temppointer.preelem = neu;
				neu.preelem.nextelem = neu;

				//Selbes element -> nicht einfuegen//					
				//Ueberpruefen welches der zwei elemente hoeher ist,setzen des head dementsprechend 
				if((neu.valueelem != temppointer.valueelem) && !neu.faster(head.valueelem))
				{	
					head = neu;
				}
			}
			//ab min 2 Elementen in der vorh. Liste
			else
			{
				//Durchgehen der Liste
				for(int i = 1;i<=n;i++)
				{
					//neues Element  == gespeichertes Element
					if(neu.valueelem == temppointer.valueelem)
					{
						check = false;
						break;
					}
					
					//Ist element nicht groesse dann einfuegen an pos
					if(!neu.faster(temppointer.valueelem))
					{
						neu.nextelem = temppointer;
						neu.preelem = temppointer.preelem;
						neu.nextelem.preelem = neu;
						neu.preelem.nextelem = neu;
						if(temppointer == head)
							head = neu;
						//Wenn pos gefunden break
						break;
					}
					
					//einfuegen an letzter pos
					if(temppointer.nextelem == head)
					{
						neu.nextelem = head;
						neu.preelem = head.preelem;
						neu.nextelem.preelem = neu;
						neu.preelem.nextelem = neu;
						break;
					}
					
					//Pointer eine Pos weiter
					temppointer = temppointer.getnext();
					
				}
			}
		}
		//Anzahl der Elemente in der Liste um eins erhoehen
		if(check)
			n = n+1; 
	}
	
	//Rep. Pointer auf Elemente der Liste
	protected class iterator implements iteratorInterface<Typ>
	{
		private element pointer;
		
		//Pointer auf erstes Element in der Liste setzen
		iterator()
		{
			pointer = head;
		}
		
		//Gibt das naechste Element zurueck und verschiebt Pointer auf dieses
		//Out: Typ(Racer,Fuse,...)
		public Typ next() 
		{
				//A elem = p.elem; p = p.next; return elem;
				pointer = pointer.getnext();
				return pointer.getvalue();		
		}
		//Gibt den aktuelle Typ zuerueck
		//Out: Typ(Racer,Fuse,...)
		public Typ getpointer()
		{
			if(pointer == null)
				return null;
			else
				return pointer.getvalue();
		}
		//Gibt zurueck ob ein naechstes Element exestiert
		//Out: boolean
		public boolean hasNext() 
		{
			//pointer auf naechstes element
			//liste leer
			if(head == null)
				return false;
			
			if(pointer.getnext() == head)
				return false;
			
			return true;
		}
		
	}
	//Erzeugt einen iterator der Liste
	//Out: class iterator();
	public iteratorInterface<Typ> iterator() 
	{
		return new iterator();
	}
	//Augabe der Werte
	
	/*
	 * Gibt alle Werte in einem String zurueck
	 * OUT: String
	 */
	public String toString()
	{
		String out ="";
		
		iteratorInterface<Typ> temp_iterator = iterator();
		boolean check_pos = true;
		if(n == 0)
			check_pos = false;
		while(check_pos)
		{
			out = out + temp_iterator.getpointer().getValue()+" ";
			check_pos = temp_iterator.hasNext();
			temp_iterator.next();	
		}	
		return out;
	}
	//Ausgabe der Durchhaltzeiten
	/*
	 * Gibt das durchhaltevermoegen
	 * in einem String zurueck
	 * OUT: String
	 */
	public String toString_durchh()
	{
		String out ="";
		
		iteratorInterface<Typ> temp_iterator = iterator();
		boolean check_pos = true;
		if(n == 0)
			check_pos = false;
		while(check_pos)
		{
			out = out + temp_iterator.getpointer().getdurchh()+" ";
			check_pos = temp_iterator.hasNext();
			temp_iterator.next();	
		}		
		return out;
	}
}

